1. Field of the Invention
The present invention relates to method and apparatus for generating a graph showing an object structure, and also to data converting method, apparatus, system, and data recording medium, all of which can use the graph generating method and apparatus. The present invention is applicable to CAD (Computer Aided Design) or to solid data used in CG (Computer Graphics), for example.
2. Description of the Related Art
For describing an object such as a solid in the field of CAD or CG, approximation using polygons has been known. This method divides the surface of an object into pieces and pastes polygon patches thereon. A large number of objects have been created in the form of polygon data and saved in databases or the like. Reasons why polygon expressions have become so popular are that this method is simple and easy to understand, and that any object can be covered with triangle patches by using this method, although editing procedure may require patience.
As has been pointed out for a long time, a problem in polygon expressions is that pursuit of precision is directly linked to an increase in data amount. Since polygon itself is flat, there is no effective method but to paste smaller polygons more when smoothness of a surface is pursued or a complex shape is expressed. For example, when a figure is modeled to a reasonable precision, tens or hundreds of thousands of polygons are generally needed. A user thinks that CG can create any image, since he/she has got used to amazing images in a movie made by using the state-of-the-art CG, such as in Jurassic Park or Apollo 13. When such a request by a user needs to be fulfilled, the number of polygons naturally increases, as long as the polygon expressions are used.
Remarkable progress in recent computer hardware lies in the background of the polygon number increase. In the past several years, improvements have been made in the areas of main memory capacity, secondary storage capacity, and CPU performance. Therefore, a large amount of polygon data can be dealt with. However, as communications using the Internet is getting popular, a problem has arisen that it takes a considerable amount of time to transfer a high-resolution image via a telephone line, and it has been widely recognized that the amount of image data is generally large. If larger polygon data is to be dealt with in the future, it will be necessary to improve hardware including infrastructure such as communication lines. There seems to be no end in the "rat race" between hardware and the number of polygons.
Based on considerations of the problems described above, a variety of trials have been carried out to reduce the amount of polygon data. In Japanese Patent Laid-Open Publication No. Hei 8-153211 (Apparatus for Reducing Polygons in Computer Graphics Data), an apparatus for reducing redundant polygons in response to viewpoints has been disclosed. According to this apparatus, image drawing speed can be increased while image quality is maintained. However, this apparatus does not reduce the amount of original polygon data needed to describe an object.
In Japanese Patent Laid-Open Publication No. Hei 7-262402 (Method for Surface Description), a method has been disclosed for expressing an object contour more smoothly by converting edges of polygons into arcs, with attention paid to directions of normal vectors at end points of the edges. When the number of polygons is small, the surface of an object is generally rough. The above method mitigates this drawback to some degree. However, this method is effective only for the cases where the number of original polygons is small, and does not reduce the polygon data amount itself.
Meanwhile, there exists another method for describing an object by surface elements called parametric patches. According to the parametric patch method, a surface can generally be expressed more smoothly with comparatively small data. On page 62 of "Basics and Applications of Three-dimensional CAD" (by Hiroshi Toritani and Hiroaki Chiyokura) published by Kyoritsu Shuppan Publishers Co., a method is disclosed for pasting surface patches by generating curve meshes using characteristic lines. In this textbook, explanation regarding how to describe surface patches by equations, how to make connections between the patches smooth, and how to describe irregular shape patches other than quadrilaterals are also given.
However, the greatest problem in using surface patches lies in the difficulties in automatic processing. If the shape to be dealt with is simple such as a cylinder, it would be easy to paste patches thereon. If the shape of an object is complex, it is extremely difficult to design a system which can give theoretical or logical support to, for example, how to approximately divide the object in order to paste patches successfully, or how to carry out minimal division. Therefore, an operator generally needs to manually specify how to paste or correct and pasting patches greatly depends on the operator's experience. On the other hand, if we hold on to the polygon expression giving up free-form surface patches, there will be no prospect of future improvement, with the amount of data to describe shapes being on the rise.